METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France)<br />Workshop on Expanders and derandomization (March 21-25, 2011)<br />Mar 21, 16:30-17:30 - Zeev Dvir (Princeton U.)<br />Monotone expanders - constructions and applications<br /><br />A Monotone Expander is an expander graph which can be decomposed into a union of a constant number of monotone matchings, under some fixed ordering of the vertices. A matching is monotone if every two edges (u,v) and (u',v') in it satisfy u < u' --> v < v'. It is not clear a priori if monotone expanders exist or not. This is partially due to the fact that the natural application of the probabilistic method does not work in this special case.<br /><br />The first construction of monotone expanders with *logarithmic* degree was given in [D. Shpilka 05] and was motivated by an application to 'Dimension Expanders' (an algebraic analog of expander graphs). Later, in [Bourgain 09], a rather involved construction with constant degree was given. A simple construction with 'log-star' degree, based on the Zig-Zag product, was given in [D. Wigderson 10], together with other applications coming from the study of Turing Machines.<br /><br />This talk will survey the above results in a high-level way.
